package com.gitee.feizns.explore.data_structure.graph;

import com.gitee.feizns.explore.data_structure.graph.utils.Graph;

import java.util.Set;
import java.util.Stack;

/**
 * @author feizns
 * @since 2020/4/28
 */
public class Hierholzer {

    public static void main(String[] args) {
        Graph<String> graph = new Graph<>();

        graph.addEdge("A", "B");
        graph.addEdge("B", "A");

        graph.addEdge("A", "C");
        graph.addEdge("C", "A");

        graph.addEdge("C", "B");
        graph.addEdge("B", "C");

        graph.addEdge("B", "E");
        graph.addEdge("E", "B");

        graph.addEdge("E", "D");
        graph.addEdge("D", "E");

        graph.addEdge("B", "D");
        graph.addEdge("D", "B");

        Hierholzer h = new Hierholzer(graph);
        System.out.println(h.result("A"));
    }

    private Graph graph;

    private Graph clone;

    public Hierholzer(Graph graph) {
        this.graph = graph;
        clone = graph.clone();
        if ( !new EulerLoop(graph).hasEulerLoop() )
            throw new RuntimeException("....");
    }

    private Stack retStack = new Stack();

    private Stack curPath = new Stack();

    public Stack ret(Object start) {
        curPath.push(start);
        while ( !curPath.isEmpty() ) {
            Object peek = curPath.peek();
            Set adj = clone.adj(peek);
            if ( adj.isEmpty() )
                retStack.push(curPath.pop());
            else {
                Object next = adj.iterator().next();
                curPath.push(next);
                removeEdge(peek, next);
            }
        }
        return retStack;
    }

    public Stack result(Object start) {
        helper(start);
        return retStack;
    }

    private void helper(Object curt) {
        Set adj = clone.adj(curt);
        if ( adj.isEmpty() )
            retStack.push(curt);
        else {
            Object next = adj.iterator().next();
            removeEdge(curt, next);
            helper(next);
            helper(curt);
        }
    }

    public void removeEdge(Object s, Object t) {
        clone.adj(s).remove(t);
        clone.adj(t).remove(s);
    }

}
